#include "linked_list.h"
#include "timer.h"
#include "LazyTest.h"
#include <list>

// standard
#include <ctime>
#include <random>
#include <algorithm>


using namespace lz;
using namespace std;

template <class T>
void output(const list<T>& ls)
{
	for(list<T>::const_iterator it = ls.begin(); it != ls.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;
}

template <class T>
void sort(list<T>& ls)
{
	// Do nothing if the list has length 0 or 1.
	if (ls.size() > 2)
	{
		list<T> __carry;
		list<T> __counter[64];
		int __fill = 0;
		while (!ls.empty()) {
			__carry.splice(__carry.begin(), ls, ls.begin());
			int __i = 0;
			while(__i < __fill && !__counter[__i].empty()) {
				__counter[__i].merge(__carry); // _carry is emptied!!!
				__carry.swap(__counter[__i++]);
			}
			__carry.swap(__counter[__i]);         
			if (__i == __fill) ++__fill;

			for (int __i = 0; __i < __fill; ++__i)
				output(__counter[__i]);
		} 

		for (int __i = 1; __i < __fill; ++__i)
			__counter[__i].merge(__counter[__i-1]);
		ls.swap(__counter[__fill-1]);
	}
}




struct Node
{
public:
	Node(int _data):data(_data){}
	int data;
	Node* next;
};

Node*& next(Node* n)
{
	return n->next;
}

bool less1(Node* n1, Node* n2)
{
	return n1->data < n2->data;
}


TESTCASE(linked_list_quick_sort)
{
	std::tr1::mt19937 eng;
	eng.seed(time(NULL));
	std::tr1::uniform_int<int> unif(-10000, 10000);


	// compare sort performance of:
	// raw list, std::list and std::vector
	// 1. placement new to group node together
	// 2. Store pointer in vector

	int num = 10000000;

	// initialize data in 3 containers
	vector<int> vec;
	list<int>   ls;
	Node*		myls = NULL;

	int val = unif(eng);

	vec.push_back(val);
	ls.push_back(val);
	myls = new Node(val);

	num--;

	Node* cur = myls;
	while(num--)
	{
		int val = unif(eng);

		vec.push_back(val);
		ls.push_back(val);

		cur->next = new Node(val);
		cur = cur->next;

	}
	cur->next = NULL;



	//// copy to vector ,sort and copy back
	//{
	//	CAutoTimer at;
	//	cout << "copy and vector: ";
	//	vector<int> v;
	//	
	//	Node* temp = myls;
	//	while(temp)
	//	{
	//		v.push_back(temp->data);
	//		temp = temp->next;
	//		
	//	}
	//	std::sort(vec.begin(), vec.end());
	//}


	// vector sort
	//
	//
	{
		CAutoTimer at;
		cout << "std::vector: ";
		std::sort(vec.begin(), vec.end());
	}

	// list sort
	{
		CAutoTimer at;
		cout << "std::list: ";
		ls.sort();
	}


	// my list sort
	{
		Node* iter = NULL;
		CAutoTimer at;
		cout << "linked list: ";
		iter = quick_sort<Node*>(myls, NULL, next, less1);
	}

	// 
}